/*
Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

*/
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
	int myMinimus(int a, int b)
	{
		return a <= b ? a:b;
		
	}
    int minPathSum(vector<vector<int> > &grid) {
        if(grid.size() == 0)
			return 0;
		int m = grid.size();
		int n = grid[0].size();
		
		vector<int> vecLevel(n,0);
		vector<vector<int> > stepTable(m,vecLevel);
		
		stepTable[0][0] = grid[0][0];
		
		for(int i = 1; i < m; i++)
		{
			stepTable[i][0] = stepTable[i-1][0] + grid[i][0];
		}
		for(int j = 1; j < n; j++ )
		{
			stepTable[0][j] = stepTable[0][j-1] +  grid[0][j];
		}
		
		for(int i = 1; i < m; i++)
		{
			for(int j = 1; j < n; j++)
			{
				stepTable[i][j] = myMinimus(grid[i][j]+stepTable[i-1][j],grid[i][j]+stepTable[i][j-1]);
			}
			
		}
		return stepTable[m-1][n-1];
    }
};


int main()
{
	cout<<"Minimum Path Sum"<<endl;
	int a1[] = {1,2,3,4,5};
	int a2[] = {5,3,4,3,1};
	int a3[] = {2,1,4,5,3};
	vector<int> vecInt1(a1, a1 + sizeof(a1)/sizeof(int));
	vector<int> vecInt2(a2, a2 + sizeof(a2)/sizeof(int));
	vector<int> vecInt3(a3, a3 + sizeof(a3)/sizeof(int));
	
	vector<vector<int> > grid;
	grid.push_back(vecInt1);
	grid.push_back(vecInt2);
	grid.push_back(vecInt3);
	
	Solution s;
	int result = s.minPathSum(grid);
	cout<<result<<endl;
	
	return 0;
}

